/*****************************************************************************
 * 
 * Copyright [2013] [Mervin.Wong]
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *       http://www.apache.org/licenses/LICENSE-2.0
 *       
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *  
 *****************************************************************************/
package base.feature;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import util.D;
import util.FibonacciHeap;
import util.MathTool;
import util.PairList;
import base.Global.NetType;
import base.Network;

/**
 * Path.java
 * 
 *@author 王进法<Mervin.Wong>
 *@version 
 *@Date 2013-1-13上午11:18:37
 */
/*********************************************************************************
 *
 *
 *
 *
 **********************************************************************************/

public class Path implements InterfacePath{
	private Network net = null;
	
	public Path(){
		
	}
	public Path(Network net){
		this.net = net;
	}
	public void set(Network net){
		this.net = net;
	}
	public Network get(){
		return this.net;
	}
	/**
	 * 
	 *  bothNodesPath
	 *  计算两个节点间的路径
	 * @param preNodeId
	 * @param postNodeId
	 * @return ArrayList<ArrayList<Number>> path 保存节点的ID
	 * YEN算法，k短路径
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<Stack<Number>> bothNodesPath(Number preNodeId, Number postNodeId){
		/*
		 * 在此函数中假设节点的id不能为-1
		 */
		ArrayList<Stack<Number>> pathList = new ArrayList<Stack<Number>>();//路径列表
		Stack<Number> tempPath = new Stack<Number>();//存放从源点到当前节点的路径。
		
		Stack<Number> stack = new Stack<Number>();//存储遍历的节点
		stack.push(preNodeId);
		
		Number nodeId = null;
		HashSet<Number> nodeAdjSet = new HashSet<Number>();
		while(!stack.empty()){
			nodeId = stack.pop();
			/**
			 * －1作为标记位，如果栈弹出的是-1，那么路径就回退一个元素
			 */
			if(nodeId.equals(-1)){
				tempPath.pop();
				continue;
			}
			
			tempPath.push(nodeId);
			
			if(nodeId.equals(postNodeId)){
				//输出次路径
				pathList.add((Stack<Number>) tempPath.clone());
				//弹出刚刚压缩栈的nodeId=postNodeId
				tempPath.pop();
				continue;
			}
			nodeAdjSet = this.net.getAdjNodesId(nodeId);//获取此点的邻接点
			stack.push(-1);
			for (Iterator<Number> iterator = nodeAdjSet.iterator(); iterator.hasNext();) {
				nodeId= (Number) iterator.next();
				//过滤掉回路
				//保证路径中的节点是唯一的
				if(!nodeId.equals(preNodeId) && !tempPath.contains(nodeId)){
					stack.push(nodeId);
				}
			}
		}
		return pathList;
	}
	
	/**
	 *  bothNodesPath
	 *  计算两个节点间的路径
	 * @param Network net
	 * @param preNodeId
	 * @param postNodeId
	 * @returnArrayList<Stack<Number>> path 保存节点的ID
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<Stack<Number>> bothNodesPath(Network net,  Number preNodeId, Number postNodeId){
		/*
		 * 在此函数中假设节点的id不能为-1
		 */
		ArrayList<Stack<Number>> pathList = new ArrayList<Stack<Number>>();//路径列表
		Stack<Number> tempPath = new Stack<Number>();//存放从源点到当前节点的路径。
		
		Stack<Number> stack = new Stack<Number>();//存储遍历的节点
		stack.push(preNodeId);
		
		Number nodeId = null;
		HashSet<Number> nodeAdjSet = new HashSet<Number>();
		while(!stack.empty()){
			nodeId = stack.pop();
			/**
			 * －1作为标记位，如果栈弹出的是-1，那么路径就回退一个元素
			 */
			if(nodeId.equals(-1)){
				tempPath.pop();
				continue;
			}
			
			tempPath.push(nodeId);
			
			if(nodeId.equals(postNodeId)){
				//输出次路径
				pathList.add((Stack<Number>) tempPath.clone());
				//弹出刚刚压缩栈的nodeId=postNodeId
				tempPath.pop();
				continue;
			}
			nodeAdjSet = net.getAdjNodesId(nodeId);//获取此点的邻接点
			stack.push(-1);
			for (Iterator<Number> iterator = nodeAdjSet.iterator(); iterator.hasNext();) {
				nodeId= (Number) iterator.next();
				//过滤掉回路
				//保证路径中的节点是唯一的
				if(!nodeId.equals(preNodeId) && !tempPath.contains(nodeId)){
					stack.push(nodeId);
				}
			}
		}
		return pathList;		
	}

	/**
	 *  bothNodesPathLength
	 *  节点间的路径长度
	 * @param preNodeId
	 * @param postNodeId
	 * @return int length
	 */
	public int bothNodesPathLength(Number preNodeId, Number postNodeId){
		return this.bothNodesPathLength(net, preNodeId, postNodeId);
	}
	
	/**
	 *  bothNodesPathLength
	 *  节点间的路径长度
	 * @param Network net
	 * @param preNodeId
	 * @param postNodeId
	 * @return int length
	 */
	public int bothNodesPathLength(Network net,  Number preNodeId, Number postNodeId){
		//HashMap<Number, Number> parent = new HashMap<Number, Number>();//前驱节点
		HashMap<Number, Integer> distance = new HashMap<Number, Integer>();//源点s到达Number的距离
		HashSet<Number> s = new HashSet<Number>();//已遍历的节点
		Set<Number> q = net.topology.keySet();//未遍历的节点
		
		Number nodeId = null;
		FibonacciHeap heap = new FibonacciHeap();
		int weight = 0;
		
		
		Iterator<Number> it = q.iterator();
		while (it.hasNext()) {
			nodeId = it.next();
			if(!nodeId.equals(preNodeId)){
				weight = net.getEdgeWeight(preNodeId, nodeId);
				if(weight >= 0){
					heap.insert(nodeId, weight);
					distance.put(nodeId, weight+100);
				}else{
					heap.insert(nodeId, Integer.MAX_VALUE);
				}
				distance.put(nodeId, Integer.MAX_VALUE);
			}else{
				heap.insert(nodeId, 0);
				distance.put(preNodeId, 0);
			}
		}
		
		HashSet<Number> adjNodes = null;
		Number adjNodeId = null;
		int edgeWeight = 0;
		while(heap.nodeNum > 0){
			nodeId = heap.extractMinNodeId();
			s.add(nodeId);
			adjNodes = net.getAdjNodesId(nodeId);
			for (Iterator<Number> iterator = adjNodes.iterator(); iterator.hasNext();) {
				adjNodeId = (Number) iterator.next();
				if(!s.contains(adjNodeId)){
					edgeWeight = net.getEdgeWeight(nodeId, adjNodeId);
					heap.decreaseNode(adjNodeId, edgeWeight);//修改节点的值
					
					weight = distance.get(nodeId)+edgeWeight;
					if(distance.get(adjNodeId) > weight){
						distance.put(adjNodeId, weight);
						//parent.put(adjNodeId, nodeId);
					}
				}
			}
		}
		if(distance.get(postNodeId) != null){
			return distance.get(postNodeId);
		}else{
			return 0;
		}
	}
	/**
	 *  bothNodesShortestPath
	 * @descripion 两点之间的最短路径 可能存在多条, 目前只求取一条路径
	 * @param preNodeId
	 * @param postNodeId
	 * @return
	 */
	public LinkedList<Number> bothNodesShortestPath(Number preNodeId, Number postNodeId){
		return bothNodesShortestPath(this.net, preNodeId, postNodeId);
	}
	
	/**
	 *  bothNodesShortestPath
	 * @descripion 两点之间的最短路径 可能存在多条, 目前只求取一条路径
	 * @param Net
	 * @param preNodeId
	 * @param postNodeId
	 * @return
	 */
	public LinkedList<Number> bothNodesShortestPath(Network net, Number preNodeId, Number postNodeId){
		preNodeId = MathTool.str2Number(Network.getNumberType(), preNodeId.toString());
		postNodeId = MathTool.str2Number(Network.getNumberType(), postNodeId.toString());
		
		
		HashMap<Number, Number> parent = new HashMap<Number, Number>();//前驱节点
		HashMap<Number, Integer> distance = new HashMap<Number, Integer>();//源点s到达Number的距离
		HashSet<Number> s = new HashSet<Number>();//已遍历的节点
		Set<Number> q = net.topology.keySet();//未遍历的节点
		
		Number nodeId = null;
		FibonacciHeap heap = new FibonacciHeap();
		int weight = 0;
		
		
		Iterator<Number> it = q.iterator();
		while (it.hasNext()) {
			nodeId = it.next();
			if(!preNodeId.equals(nodeId)){
				weight = net.getEdgeWeight(preNodeId, nodeId);
				if(weight >= 0){
					heap.insert(nodeId, weight);
					distance.put(nodeId, weight+100);
				}else{
					heap.insert(nodeId, Integer.MAX_VALUE);
				}
				distance.put(nodeId, Integer.MAX_VALUE);
			}else{
				heap.insert(nodeId, 0);
				distance.put(preNodeId, 0);
			}
		}
		
		HashSet<Number> adjNodes = null;
		Number adjNodeId = null;
		int edgeWeight = 0;
		while(heap.nodeNum > 0){
			nodeId = heap.extractMinNodeId();
			s.add(nodeId);
			//D.p("extract"+nodeId);
			adjNodes = net.getAdjNodesId(nodeId);
			for (Iterator<Number> iterator = adjNodes.iterator(); iterator.hasNext();) {
				adjNodeId = (Number) iterator.next();
				if(!s.contains(adjNodeId)){
					edgeWeight = net.getEdgeWeight(nodeId, adjNodeId);
					heap.decreaseNode(adjNodeId, edgeWeight);//修改节点的值
					
					weight = distance.get(nodeId)+edgeWeight;
					if(distance.get(adjNodeId) > weight){
						distance.put(adjNodeId, weight);
						parent.put(adjNodeId, nodeId);
					}
				}
			}
		}
		
		LinkedList<Number> path = new LinkedList<Number>();
		path.addFirst(postNodeId);
		nodeId = parent.get(postNodeId);
		if(nodeId != null){
			while(!nodeId.equals(preNodeId)){
				path.addFirst(nodeId);
				nodeId = parent.get(nodeId);
			}
			path.addFirst(preNodeId);
		}
		return path;		
	}
	
/*	*//**
	 * 使用上面的Dijkstra->
	 *  netDiameter
	 *  网络直径
	 * @return
	 * 
	 *//*
	public int netDiameter(){
		return this.netDiameter(this.net);
	}
	*//**
	 *  netDiameter
	 *  网络直径
	 * @param net
	 * @return
	 *//*
	public int netDiameter(Network net){
		Set<Number> nodesId = net.topology.keySet();
		HashSet<Number> visited = new HashSet<Number>();
		Number nodeId = null;
		for (Iterator<Number> iterator = nodesId.iterator(); iterator.hasNext();) {
			nodeId = (Number) iterator.next();
			visited.add(nodeId);
			
			
		}
		return 0;
	}
	*//**
	 *  netAvgPathLength 
	 *  网络的平均路径长度
	 * @return
	 *//*
	public double netAvgPathLength(){
		return this.netAvgPathLength(this.net);
	}
	
	*//**
	 * 
	 *  netAvgPathLength 
	 *  网络的平均路径长度
	 * @param Network net
	 * @return
	 *//*
	public double netAvgPathLength(Network net){
		HashMap<Number, Integer> distance = null;//源点s到达Number的距离
		Set<Number> nodesId = net.topology.keySet();
		Number nodeId1 = null, nodeId2;
		int sum = 0, count = 0, len = 0;
		for (Iterator<Number> iterator = nodesId.iterator(); iterator.hasNext();) {
			nodeId1 = (Number) iterator.next();
			distance = this.bothNodesShortestPathLen(net, nodeId1);
			for (Iterator<Number> iterator2 = distance.keySet().iterator(); iterator2.hasNext();) {
				nodeId2 = (Number) iterator2.next();
				len = distance.get(nodeId2);
				if(len < Integer.MAX_VALUE){
					sum += len;
				}
			}
			count += distance.size()-1;
		}
		return (double)sum/count;
	}*/
	
	private HashMap<Number, Integer> bothNodesShortestPathLen(Network net, Number preNodeId){
		HashMap<Number, Integer> distance = new HashMap<Number, Integer>();//源点s到达Number的距离
		HashSet<Number> s = new HashSet<Number>();//已遍历的节点
		Set<Number> q = net.topology.keySet();//未遍历的节点
		
		Number nodeId = null;
		FibonacciHeap heap = new FibonacciHeap();
		int weight = 0;
		
		Iterator<Number> it = q.iterator();
		while (it.hasNext()) {
			nodeId = it.next();
			if(!nodeId.equals(preNodeId)){
				weight = net.getEdgeWeight(preNodeId, nodeId);
				if(weight >= 0){
					heap.insert(nodeId, weight);
					distance.put(nodeId, weight+100);
				}else{
					heap.insert(nodeId, Integer.MAX_VALUE);
				}
				distance.put(nodeId, Integer.MAX_VALUE);
			}else{
				heap.insert(nodeId, 0);
				distance.put(preNodeId, 0);
			}
		}
		
		HashSet<Number> adjNodes = null;
		Number adjNodeId = null;
		int edgeWeight = 0;
		while(heap.nodeNum > 0){
			nodeId = heap.extractMinNodeId();
			s.add(nodeId);
			//D.p("extract"+nodeId);
			adjNodes = net.getAdjNodesId(nodeId);
			for (Iterator<Number> iterator = adjNodes.iterator(); iterator.hasNext();) {
				adjNodeId = (Number) iterator.next();
				if(!s.contains(adjNodeId)){
					edgeWeight = net.getEdgeWeight(nodeId, adjNodeId);
					heap.decreaseNode(adjNodeId, edgeWeight);//修改节点的值
					
					weight = distance.get(nodeId).intValue()+edgeWeight;
					if(distance.get(adjNodeId).intValue() > weight){
						distance.put(adjNodeId, weight);
					}
				}
			}
		}
		
		return distance;		
	}
	/********************************************************************************************************
	 * 
	 * 
	 * 
	 *******************************************************************************************************/
	/**
	 * 使用上面的Dijkstra->
	 *  netDiameter
	 *  网络直径
	 * @return
	 * 
	 */
	public int netDiameter(){
		return this.netDiameter(this.net);
	}
	/**
	 *  netDiameter
	 *  网络直径
	 * @param net
	 * @return
	 */
	public int netDiameter(Network net){
		int diameter = 0, level = 0;
		
		Set<Number> nodesId = net.topology.keySet();//网络中的所有节点
		Network net2 = null;//每个节点的最短路径网
		Number nodeId = null, adjNodeId = null;
		HashSet<Number> adjNodesId = null;
		HashSet<Number> s = new HashSet<Number>();//访问的节点
		Queue<Number> queue = new LinkedList<Number>();;//访问了该节点，但是没有遍历该节点的邻接点
		for (Iterator<Number> iterator = nodesId.iterator(); iterator.hasNext();) {
			level = 0;//初始化
			nodeId = (Number) iterator.next();
			s.clear();
			queue.clear();
			queue.offer(nodeId);
			queue.offer(-1);
			
			net2 = this.shortestPathNet(net, nodeId);
			while(queue.size() > 1){
				nodeId = queue.poll();
				if(nodeId.equals(-1)){
					queue.offer(-1);
					level++;
					continue;
				}else{
					s.add(nodeId);
				}
				//D.p(nodeId);
				adjNodesId = net2.getAdjNodesId(nodeId);
				for (Iterator<Number> iterator1 = adjNodesId.iterator(); iterator1.hasNext();) {
					adjNodeId = (Number) iterator1.next();
					if(!s.contains(adjNodeId)){
						s.add(adjNodeId);
						queue.offer(adjNodeId);
					}
				}
			}
			if(diameter < level){
				diameter = level;
			}
		}
		return level;
	}
	/**
	 *  netAvgPathLength 
	 *  网络的平均路径长度
	 * @return
	 */
	public double netAvgPathLength(){
		return this.netAvgPathLength(this.net);
	}
	
	/**
	 * 
	 *  netAvgPathLength 
	 *  网络的平均路径长度
	 * @param Network net
	 * @return
	 */
	public double netAvgPathLength(Network net){
		HashMap<Number, int[]> distance = null;//源点s到达Number的距离
		Set<Number> nodesId = net.topology.keySet();
		Number nodeId1 = null, nodeId2;
		int[] temp = new int[2];
		int sum = 0, count = 0, len = 0;
		for (Iterator<Number> iterator = nodesId.iterator(); iterator.hasNext();) {
			nodeId1 = (Number) iterator.next();
			distance = this.bothNodesDiameter(net, nodeId1);
			//D.m();
			for (Iterator<Number> iterator2 = distance.keySet().iterator(); iterator2.hasNext();) {
				nodeId2 = (Number) iterator2.next();
				temp = distance.get(nodeId2);
				len = temp[0]*temp[1];
				sum += len;
				count += temp[1];
			}
			//count += distance.size()-1;
		}
		return (double)sum/count;
	}
	
	/**
	 *  bothNodesDiameter
	 * @param net
	 * @param proNodeId
	 * @param postNodeId
	 * @return
	 */
	public int bothNodesDiameter(Network net, Number proNodeId, Number postNodeId){
		
		Set<Number> nodesId = net.topology.keySet();//网络中的所有节点
		if(nodesId.contains(postNodeId)){
			//HashMap<Number, Number> parent = new HashMap<Number, Number>();//记录该节点的父节点
			HashSet<Number> s = new HashSet<Number>();//访问且遍历完的节点
			Queue<Number> queue = new LinkedList<Number>();;//访问了该节点，但是没有遍历该节点的邻接点
			queue.offer(proNodeId);
			queue.offer(-1);
			
			Number nodeId = null, adjNodeId = null;
			HashSet<Number> adjNodesId = null;
	 		int level = 1;
			while(!queue.isEmpty()){
				nodeId = queue.poll();
				if(nodeId.equals(-1)){
					queue.offer(-1);
					level++;
					continue;
				}else{
					s.add(nodeId);
				}
				//D.p(nodeId);
				adjNodesId = net.getAdjNodesId(nodeId);
				for (Iterator<Number> iterator = adjNodesId.iterator(); iterator.hasNext();) {
					adjNodeId = (Number) iterator.next();
					if(adjNodeId.equals(postNodeId)){
						return level;
					}
					if(!s.contains(adjNodeId)){
						queue.offer(adjNodeId);
					}
				}
			}
			return -1;
		}else{
			return -1;
		}
	}
	/**
	 * 只计算距离
	 *  bothNodesDiameter
	 * @param net 如果是加权网络，需要net为最短路径网络，如果是非加权网络，可以是原始网络
	 * @param proNodeId
	 * @return
	 */
	public HashMap<Number, int[]> bothNodesDiameter(Network net, Number preNodeId){
		//Set<Number> nodesId = net.topology.keySet();//网络中的所有节点
		HashMap<Number, Integer> distance = new HashMap<Number, Integer>();
		HashMap<Number, Integer> nums = new HashMap<Number, Integer>();
		HashMap<Number, int[]> diameter = new HashMap<Number, int[]>();
		//HashMap<Number, Number> parent = new HashMap<Number, Number>();//记录该节点的父节点
		HashSet<Number> s = new HashSet<Number>();//访问的节点
		HashSet<Number> visit = new HashSet<Number>();//访问的节点
		Queue<Number> queue = new LinkedList<Number>();;//访问了该节点，但是没有遍历该节点的邻接点
		queue.offer(preNodeId);
		queue.offer(-1);
		visit.add(preNodeId);
		
		Number nodeId = null, adjNodeId = null;
		HashSet<Number> adjNodesId = null;
		int[] temp = new int[2];
 		int level = 1;
		while(queue.size() > 1){
			nodeId = queue.poll();
			if(nodeId.equals(-1)){
				queue.offer(-1);
				level++;
				continue;
			}else{
				s.add(nodeId);
				visit.remove(nodeId);
			}
			//D.p(nodeId);
			adjNodesId = net.getAdjNodesId(nodeId);
			for (Iterator<Number> iterator = adjNodesId.iterator(); iterator.hasNext();) {
				adjNodeId = (Number) iterator.next();
				if(!s.contains(adjNodeId)){
					//没有遍历过
					D.p(preNodeId+"####"+nodeId+"###"+adjNodeId);
					if(visit.contains(adjNodeId)){
						//非第一次访问
						 if(distance.get(adjNodeId) >= level){
							 nums.put(adjNodeId, nums.get(adjNodeId)+1);
							 temp = diameter.get(adjNodeId);
							 temp[1] = temp[1]+1;
							 diameter.put(adjNodeId, temp);
						 }
					}else{
						//第一次访问
						visit.add(adjNodeId);
						temp[0] = level;
						temp[1] = 1;
						diameter.put(adjNodeId, temp);
						nums.put(adjNodeId, 1);
						distance.put(adjNodeId, level);
						queue.offer(adjNodeId);
					}
					//s.add(adjNodeId);
					//D.p(preNodeId+"###"+adjNodeId+"@@@"+level);
				}
			}
		}
		//return distance;
		return diameter;
	}
	/**
	 *  shortestPathNet
	 *  从一个节点到所有节点的最短路径网
	 * @param net
	 * @param preNodeId
	 * @return
	 */
	public Network shortestPathNet(Network net, Number preNodeId){
		preNodeId = MathTool.str2Number(Network.getNumberType(), preNodeId.toString());
		
		HashSet<Number> s = new HashSet<Number>();//已遍历的节点
		
		HashMap<Number, Integer> dist = new HashMap<Number, Integer>();//有preNodeId->v的距离 
		//HashMap<Number, LinkedList<Number>> edges = new HashMap<Number, LinkedList<Number>>(); 
		PairList<Number, Number> edges = new PairList<Number, Number>();
		
		Set<Number> q = net.topology.keySet();//所有的节点
		FibonacciHeap heap = new FibonacciHeap();//斐波那契堆
		Iterator<Number> it = q.iterator();
		
		Number nodeId = null;
		
		while(it.hasNext()){
			nodeId = it.next();
			if(nodeId.equals(preNodeId)){
				heap.insert(nodeId, 0);
				dist.put(nodeId, 0);
			}else{
				heap.insert(nodeId, Integer.MAX_VALUE);
				dist.put(nodeId, Integer.MAX_VALUE);
			}
		}
		
		HashSet<Number> adjNodesId = null;
		Number adjNodeId = null;
		int weight = 0;
		while(heap.nodeNum > 0){
			nodeId = heap.extractMinNodeId();
			s.add(nodeId);
			adjNodesId = net.getAdjNodesId(nodeId);
			for (Iterator<Number> iterator = adjNodesId.iterator(); iterator.hasNext();) {
				adjNodeId = (Number) iterator.next();
				if(!s.contains(adjNodeId)){
					weight = net.getEdgeWeight(nodeId, adjNodeId)+dist.get(nodeId);
					if(weight < dist.get(adjNodeId)){
						//小于
						dist.put(adjNodeId, weight);
						//D.p(preNodeId+"@@@@"+adjNodeId+"###"+weight);
						heap.decreaseNode(adjNodeId, weight);
						//删除原来的目的节点是adjNodeId边
						edges.removeByR(adjNodeId);
						//添加新边
						edges.add(nodeId, adjNodeId);
					}else if(weight == dist.get(adjNodeId)){
						//等于
						edges.add(nodeId, adjNodeId);
					}else{
						// 大于
					}
				}
			}
		}
		Network net1 = new Network(edges, Network.netType, Network.getNumberType());
		return net1;
	}

	public static void main(String[] args){
		Network net = new Network("../data/ipp/net11.txt", NetType.UNDIRECTED);
		Path p = new Path(net);
		D.p(p.netAvgPathLength());
		p.bothNodesDiameter(net, 11);
		D.m();
		//D.p(p.netDiameter());
		//p.shortestPathNet(net, 6);
	}
}
